Search for: All records

Abstract The theory of forbidden 0–1 matrices generalizes Turán-style (bipartite) subgraph avoidance, Davenport-Schinzel theory, and Zarankiewicz-type problems, and has been influential in many areas, such as discrete and computational geometry, the analysis of self-adjusting data structures, and the development of the graph parametertwin width. The foremost open problem in this area is to resolve thePach-Tardos conjecturefrom 2005, which states that if a forbidden pattern$$P\in \{0,1\}^{k\times l}$$ $P\in {\{0,1\}}^{k\times l}$isacyclic, meaning it is the bipartite incidence matrix of a forest, then$$\operatorname {Ex}(P,n) = O(n\log ^{C_P} n)$$ $Ex(P,n)=O\left(n{log}^{C_P}n\right)$, where$$\operatorname {Ex}(P,n)$$ $Ex(P,n)$is the maximum number of 1s in aP-free$$n\times n$$ $n\times n$0–1 matrix and$$C_P$$ $C_P$is a constant depending only onP. This conjecture has been confirmed on many small patterns, specifically allPwith weight at most 5, and all but two with weight 6. The main result of this paper is a clean refutation of the Pach-Tardos conjecture. Specifically, we prove that$$\operatorname {Ex}(S_0,n),\operatorname {Ex}(S_1,n) \ge n2^{\Omega (\sqrt{\log n})}$$ $Ex(S_0,n),Ex(S_1,n)\ge n{2}^{\Omega \left(\sqrt{logn}\right)}$, where$$S_0,S_1$$ $S_0,S_1$are the outstanding weight-6 patterns. We also prove sharp bounds on the entire class ofalternatingpatterns$$(P_t)$$ $\left(P_t\right)$, specifically that for every$$t\ge 2$$ $t\ge 2$,$$\operatorname {Ex}(P_t,n)=\Theta (n(\log n/\log \log n)^t)$$ $Ex(P_t,n)=\Theta \left(n{(logn/loglogn)}^t\right)$. This is the first proof of an asymptotically sharp bound that is$$\omega (n\log n)$$ $\omega (nlogn)$.